typedef int HPDataType;
//
typedef struct Heap
{
    HPDataType* a;	//堆结构是基于数组结构实现的
    int size;		//数组下标
    int capacity; 	//数组容量
}Heap;

//堆的初始化
void HeapInit(Heap* hp) {
    assert(hp);
    hp->a = NULL;
    hp->size = hp->capacity = 0;
}

// 堆的销毁
void HeapDestory(Heap* hp) {
    assert(hp);
    free(hp->a);
    hp->a = NULL;
    hp->size = hp->capacity = 0;
}

// 取堆顶的数据
HPDataType HeapTop(Heap* hp) {
    assert(hp);
    assert(hp->size > 0);
    return hp->a[0];
}

// 堆的数据个数
int HeapSize(Heap* hp) {
    assert(hp);
    return hp->size;
}

// 堆的判空
int HeapEmpty(Heap* hp) {
    assert(hp);
    return hp->size == 0;
}

//////////////////////////////////////////////////////////////////////////////////

//数据交换函数
void Swap(HPDataType* p1, HPDataType* p2) {//交换的是数组中两个地址指向的数据
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}


////////////////////////////////////////////////////////////////////////////////

//向上调整算法
void AdjustUp(HPDataType* a, int child) {
    int parent = (child - 1) / 2;	//无论是奇偶子节点，均可以通过数组的下标“-1再/2”来获得父节点的下标

    //while (parent >= 0) 为了防止数组的越界访问，我们不采取这个循环条件
    while (child > 0)
    {
        if (a[child] < a[parent])		//如果子节点小于父节点
        {
            Swap(&a[child], &a[parent]);	//使用交换函数，交换父子的数据
            //当子节点与根节点完成交换之后，就归到其根节点的父节点所在的子树进行调整了
             //之前交换的父节点也就成为了也就成为了现在要调整的树的子节点
            child = parent;
            parent = (child - 1) / 2;	//重新获取现在要调整的树的根节点		
        }
        else
        {
            break;						//如果子节点大于父节点就不需要调整了
        }
    }
}

// 堆的插入
void HeapPush(Heap* hp, HPDataType x) {
    //判空
    assert(hp);

    //若空间不足则扩容
    if (hp->size == hp->capacity) {
        int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
        //realloc记得传入要扩容的数组地址
        HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
        if (tmp == NULL) {
            perror("realloc fail");
            return;
        }
        hp->a = tmp;
        hp->capacity = newcapacity;
    }

    //插入并向上调整
    hp->a[hp->size] = x;
    hp->size++;
    Adjustup(hp->a, hp->size - 1);

}



////////////////////////////////////////////////////////////////////////////////


//向下调整有一个大前提：左右子树必须已经是一个堆，才能调整
//向下调整算法--可以将数组恢复成堆的顺序--小根堆
void AdjustDown(HPDataType* a, int n, int parent) {//传入的数组的地址和数组数据总个数还有根节点的位置
    //传入根节点的位置是因为需要调整的元素的位置就是根位置

    //利用假设法--先假设左孩子小，因为左孩子更不容易越界
    int child = parent * 2 + 1;//找到根节点的左子节点

    while (child < n) {//child >= n 说明孩子不存在，已经调整到叶子节点了
        //找出两个子节点中较小的那个与根节点进行比较看是否要交换
        if (child + 1 < n && a[child + 1] < a[child]) {
            ++child;
        }
        //如果子节点小于根节点，则进行值的交换
        if (a[child] < a[parent]) {
            Swap(&a[child], &a[parent]);
            //当根节点与左右子节点其中之一交换完成后，就应该递到交换的子树中进行调整了
             //之前交换的子节点也就成为了现在要调整的树的根节点
            parent = child;		//现在要调整的树的根节点是之前交换的子结点
            child = parent * 2 + 1;//重新获取现在要调整的树的子节点
        }
        else {
            break;	////如果最小的节点都大于父节点了，就说明不需要调整了
        }
    }
}


// 堆的删除--是删除堆顶的数据，将堆顶的数据跟最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
//这样可以保持除堆顶以外的元素仍然能保持堆的顺序，可以大大提升效率
void HeapPop(Heap* hp) {
    assert(hp);
    assert(hp->size > 0);
    Swap(&hp->a[0], &hp->a[hp->size - 1]);
    hp->size--;
    AdjustDown(hp->a, hp->size, 0);
}



///////////////////////////////////////////////////////////////////////////////////
/*
//堆的创建，递归向下调整--大根堆当某个节点的值小于其子节点时，通过调整使其满足堆的性质。
void heapifyDown(heap* hp, int index) {
    int largest = index;//记录当前子树中最大值的索引
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    //通过比较取得子树中最大的那个节点索引
    if (left < hp->size && hp->a[left] > hp->a[largest])
        largest = left;

    if (right < hp->size && hp->a[right] > hp->a[largest])
        largest = right;

    //如果最大值不是当前节点则调整，是则结束递归
    if (largest != index) {
        swap(&hp->a[index], &hp->a[largest]);//交换当前节点与最大子节点的值
        //这个时候largest指向的节点是换下来的小节点，而不是原先的最大子节点
        heapifyDown(hp, largest);//递到下一层调整被交换下去的小节点
    }
}
*/